(1) Field of the Invention
The present invention relates to an input data interleaving device and method, and more particularly to a memory size allocation device and method adopted for use in an interleaving process.
(2) Description of the Related Art
Data interleaving is a commonly used method for data protection to reduce error possibility during transmission. Before the data interleaving is adopted, data are transmitted by individual cluster. Namely the non-interleaved data are transmitted by a cluster at an interval unit to the receiving end. During the data transmission process, transmission environments or other factors often cause data loss. As a result, data missing could occur to the whole clustered data and the message could not be interpreted or understood. To remedy this problem, an interleaving process is often adopted before data transmission to delay transmission of a plurality of data in a cluster rather than transmit them together. Hence even if data loss occurred, it does not happen to the same cluster of data and is distributed in different data clusters. The loss impact can be minimized, and the message can still be interpreted.
Refer to FIG. 1 for a conventional interleaver 10 and a memory 12. For the input data contains two data clusters, and each data cluster has seven data items, the data items of the data clusters are input at each interval unit to the interleaver 10 which processes the input data according to an interleaving process, and the memory 12 buffers the data items not yet output according to the requirement of the interleaver 10. Under the coordination of the interleaver 10 and the memory 12, output of the data items in one cluster may be delayed. As shown in FIG. 1, in the time sequences T1 and T2, the interleaver 10 receives sequentially two data clusters G1 and G2. Each data cluster has seven data items marked respectively by G10˜G16 and G20˜G26. Then the interleaver 10 outputs data items according to a selected delay D (such as 1 T). Hence the interleaver 10 outputs data item G10 at T1, outputs data items G11and G2at T2, outputs data items G12 and G21 at T3, and so on, outputs data items G16 and G25 at T7, and outputs the last data item G26 at T8. By means of the aforesaid process, the data of two input data clusters become delayed output data through the interleaver 10. In practice, the interleaver 10 continuously receives and outputs data. Hence if there are seven data items in each input, the output after the interleaving process also have seven data items belong to input data items of different sequence. Therefore the probability of losing the entire data cluster decreases.
The interleaver 10 initially buffers the delay output data in the memory 12, then outputs the data items when the output process arrives. In the conventional memory 12, the allocated memory size has to be at least (N+1)×ND to sustain the buffered data during the output process without being overlaid by the follow on input data. N+1is the number of data items in each data cluster. ND is the output sequence of the last data item. Take FIG. 1 as an example, there are 6+1 data items, the maximum delay is 6D, given the condition of D=T=1, the memory 12 has to include at least (6+1)×6=42 memory addresses to buffer the continuously input data clusters.
While the conventional approach for memory allocation can prevent the delayed data to be overlaid by the follow on input data, it wastes a lot of memory addresses because of each data cluster includes N+1 data items and occupies N+1 memory addresses after input. These memory addresses are reserved for data cluster buffering and released for input data cluster until the last data item of the data cluster has been output. The previous discussion indicates that the data items in the data clusters are output sequentially. When the last data item is output, the buffered memory addresses no longer have buffered data. To release the buffered memory for the follow on input data clusters until the last data item is output causes waste of memory addresses and a lower memory utilization efficiency. There is a need to develop an improved memory size allocation system and method to free the memory address that originally buffers a certain data item of a data cluster after that data item has been output and release the memory address for the follow on data to use.